#include <iostream>
#include "tree_functions.h"
#include <math.h>
#include <string.h>



using namespace std;

void Index::printKeys() {
	Node *node = root;

	while(node->id != LEAFID) {
		node = ((IndexNode *)node)->nodePtrs[0];
	}

	while(node != NULL) {
		printKeysNode(node);
		node = ((LeafNode *)node)->nextLeaf;
	}
}

Record * Index::searchRecord(int searchKey) {
	Node *currentNode = root;
	while(currentNode->id != LEAFID) {
		int x = 0;
		while(searchKey > currentNode->keys[x]) {
			x++;
			if(x == currentNode->q)
				break;
		}
		currentNode = ((IndexNode *)currentNode)->nodePtrs[x];
	}
	return  returnRecordInLeaf(searchKey, (LeafNode *)currentNode);

}

Record * Index::returnRecordInLeaf(int searchKey, LeafNode *leaf) {
	for(int x=0; x < leaf->q; x++) {
		if(leaf->keys[x] == searchKey) {
			return leaf->records[x];
		}
	}
	return NULL;
}

bool Index::isNodeFull(Node *node) {
	if(node->q == d)
		return true;
	else
		return false;
}

void Index::insertRecordInLeaf(LeafNode *leafNode, int key, Record* record) {

	if(leafNode->q == 0) {
		leafNode->keys[0] = key;
		leafNode->records[0] = record;
		(leafNode->q)++;
	}
	else {
		if(key > leafNode->keys[leafNode->q-1]) {
			leafNode->records[leafNode->q] = record;
			leafNode->keys[leafNode->q] = key;
			(leafNode->q)++;
		}
		else {
			for(int index=0; index < leafNode->q; index++) {
				if(key < leafNode->keys[index]) {
					//Save next entry into temp
					Record* recordTemp = leafNode->records[index];
					int keyTemp = leafNode->keys[index];

					Record* recordTemp2;
					int keyTemp2;

					//Set current index to new record
					leafNode->records[index] = record;
					leafNode->keys[index] = key;

					for(int x=index+1; x < (leafNode->q + 1); x++) {
						recordTemp2 = leafNode->records[x];
						keyTemp2 = leafNode->keys[x];

						leafNode->records[x] = recordTemp;
						leafNode->keys[x] = keyTemp;

						recordTemp = recordTemp2;
						keyTemp = keyTemp2;
					}
					(leafNode->q)++;
					break;
				}
			}
		}
	}
}

void Index::printIndex() {
	int length=0;
	Node* front= queue.front();

	if(front->id == INDEXID) {
		length = queue.size();
		printLevel();
		for(int x=0; x < length; x++) {
			Node *temp = queue.front();
			queue.pop();
			addNodesToQueue((IndexNode *)temp);
		}
		printIndex();
	}
	else {
		printLevel();
		resetQueue();
	}

}

void Index::printLevel() {
	for(int x=0; x < queue.size(); x++) {
		Node *temp = queue.front();
		queue.pop();
		printKeysNode(temp);
		queue.push(temp);
	}
	cout << endl;
}

void Index::printKeysNode(Node *node) {
	for(int x=0; x<node->q; x++) {
		if(x != node->q-1)
			cout << node->keys[x] << ", ";
		else
			cout << node->keys[x]  << "\t\t";
	}
}

void Index::addNodesToQueue(IndexNode* node) {
	for(int x=0; x<(node->q+1); x++)
		queue.push(node->nodePtrs[x]);
}



IndexNode * Index::splitLeafNode(LeafNode* originalNode) {
	int divIndex = ceil((d+1)/2) - 1;

//	LeafNode *leftLeafNode = new LeafNode();
//	leftLeafNode->q = divIndex+1;
	originalNode->q = divIndex+1;
	LeafNode *rightLeafNode = new LeafNode();
	rightLeafNode->q = d-divIndex;

	IndexNode* newRoot = new IndexNode();
	newRoot->q = 1;
	newRoot->keys[0] = originalNode->keys[divIndex];
	newRoot->nodePtrs[0] = originalNode;
	newRoot->nodePtrs[1] = rightLeafNode;

//	memcpy(leftLeafNode->keys, originalNode->keys, 4*(divIndex+1));
	memcpy(rightLeafNode->keys, &(originalNode->keys[divIndex+1]), 4*(d-divIndex));
//	memcpy(leftLeafNode->records, originalNode->records, 4*(divIndex+1));
	memcpy(rightLeafNode->records, &(originalNode->records[divIndex+1]), 4*(d-divIndex));

//	if(originalNode->previousLeaf != NULL)
//		originalNode->previousLeaf->nextLeaf = leftLeafNode;
//	if(originalNode->nextLeaf != NULL)
//		originalNode->nextLeaf->previousLeaf = rightLeafNode;
//	leftLeafNode->nextLeaf = rightLeafNode;
//	rightLeafNode->previousLeaf = originalNode;
//	leftLeafNode->previousLeaf = originalNode->previousLeaf;
	rightLeafNode->nextLeaf = originalNode->nextLeaf;
	originalNode->nextLeaf = rightLeafNode;



//	delete originalNode;
	return newRoot;
}

void Index::insertRecord(int insertKey, Record *record) {
	Node* currentNode = (stack.top())->node;


	if(searchRecord(insertKey))	//Checks if the key is already in the database before inserting
		cout << "There is already a record with the same key!!!!!" << endl;
	else {

		if(record) {	//checks to see space is available for a record insertion

			if(currentNode->id == LEAFID) {
				// The index has only the root node
				if(isNodeFull(currentNode)) {
					insertRecordInLeaf((LeafNode *)currentNode, insertKey, record);
					root = splitLeafNode((LeafNode *)currentNode);
					queue.front() = root;
					stack.top()->node = root;
				}
				else {
					insertRecordInLeaf((LeafNode *)currentNode, insertKey, record);
				}
			}
			else {	//The index tree contains at least one Index Node
				int x=0;

				//Looks for the correct index in the current Node
				while(insertKey > currentNode->keys[x]) {
					x++;
					if(x == currentNode->q)
						break;
				}

				//nextNode points to the nextNode where the record belongs
				Node* nextNode = (((IndexNode *)currentNode)->nodePtrs[x]);

				if(nextNode->id == LEAFID) {
					if(isNodeFull(nextNode)) {
						insertRecordInLeaf((LeafNode *)nextNode, insertKey, record);
						IndexNode* temp = splitLeafNode((LeafNode *)nextNode);

						if(!isNodeFull(currentNode)) {
							insertKeyInIndex((IndexNode *)currentNode, temp, x);
							resetStack();
						}
						else {
							insertKeyInIndex((IndexNode *)currentNode, temp, x);

							if(currentNode == root) {
								root = splitIndexNode((IndexNode *)currentNode);
								queue.front() = root;
								stack.top()->node = root;
								resetStack();
							}
							else {
								IndexNode* temp2 = splitIndexNode((IndexNode *)currentNode);
								stack.pop();
								while(!stack.empty()) {
									stackElement* previousStack = stack.top();
									IndexNode* previousNode = (IndexNode *)(previousStack->node);
									int index = previousStack->index;

									if(isNodeFull(previousNode)) {
										if(root == previousNode) {
											insertKeyInIndex(previousNode, temp2, index);
											root = splitIndexNode(previousNode);
											queue.front() = root;
											stack.top()->node = root;
											resetStack();
											break;
										}
										else {
											stack.pop();
											insertKeyInIndex(previousNode, temp2, index);
											temp2 = splitIndexNode(previousNode);
										}
									}
									else {
										insertKeyInIndex(previousNode, temp2, index);
										resetStack();
										break;
									}
								}
							}
						}

					}
					else {
						insertRecordInLeaf((LeafNode *)nextNode, insertKey, record);
						resetStack();
					}
				}
				else {
					stackElement *currentStack = stack.top();
					stack.pop();
					currentStack->index = x;
					stack.push(currentStack);
					stackElement *nextStack = new stackElement;
					nextStack->node = nextNode;
					nextStack->index = 0;
					stack.push(nextStack);

					insertRecord(insertKey, record);
				}
			}

		}
		else {	//Not enough space on disk for an insertion
				cout << "There is not enough space left on disk!!!!!" << endl;
		}
	}

}

void Index::insertKeyInIndex(IndexNode *node, IndexNode* temp, int index) {

	if(index == node->q) {
		node->keys[index] = temp->keys[0];
		node->nodePtrs[index] = temp->nodePtrs[0];
		node->nodePtrs[index+1] = temp->nodePtrs[1];
		(node->q)++;
	}
	else {
		Node *lastPtr = node->nodePtrs[node->q];

		Node* nodePtrTemp = temp->nodePtrs[1];
		int keyTemp = node->keys[index];

		Node* nodePtrTemp2;
		int keyTemp2;

		node->keys[index] = temp->keys[0];
		node->nodePtrs[index] = temp->nodePtrs[0];

		for(int x=index+1; x < (node->q + 1); x++) {
			nodePtrTemp2 = node->nodePtrs[x];
			keyTemp2 = node->keys[x];

			node->nodePtrs[x] = nodePtrTemp;
			node->keys[x] = keyTemp;

			nodePtrTemp = nodePtrTemp2;
			keyTemp = keyTemp2;
		}
		(node->q)++;
		node->nodePtrs[node->q] = lastPtr;
	}
}

IndexNode * Index::splitIndexNode(IndexNode *currentNode) {
	int divIndex = ceil((d+1)/2) - 1;

//	IndexNode *leftIndexNode = new IndexNode();
//	leftIndexNode->q = divIndex
	currentNode->q = divIndex;
	IndexNode *rightIndexNode = new IndexNode();
	rightIndexNode->q = d-divIndex;

	IndexNode* newRoot = new IndexNode();
	newRoot->q = 1;
	newRoot->keys[0] = currentNode->keys[divIndex];
	newRoot->nodePtrs[0] = currentNode;
	newRoot->nodePtrs[1] = rightIndexNode;

//	memcpy(leftIndexNode->keys, currentNode->keys, 4*divIndex);
	memcpy(rightIndexNode->keys, &(currentNode->keys[divIndex+1]), 4*(d-divIndex));
//	memcpy(leftIndexNode->nodePtrs, currentNode->nodePtrs, 4*(divIndex+1));
	memcpy(rightIndexNode->nodePtrs, &(currentNode->nodePtrs[divIndex+1]), 4*(d-divIndex+1));

	rightIndexNode->nextNode = currentNode->nextNode;
	currentNode->nextNode = rightIndexNode;

//	delete currentNode;
	return newRoot;
}

//Used to keep track of the current Node level while inserting
void Index::resetStack() {

while(stack.size() > 1)
	stack.pop();
}

//Used to keep track of the current Node level while printing index
void Index::resetQueue() {
while(queue.size() > 0)
	queue.pop();

queue.push(root);
}



